/*
 * @lc app=leetcode.cn id=954 lang=typescript
 *
 * [954] 二倍数对数组
 */

// @lc code=start
function canReorderDoubled(arr: number[]): boolean {
  // 每个数字出现的次数
  const map = new Map<number, number>();
  // 初始化哈希表
  for (const num of arr) {
    map.set(num, (map.get(num) || 0) + 1);
  }

  // 数字0的个数需要为偶数，因为0的另一对也是0
  if ((map.get(0) & 1) === 1) {
    return false;
  }

  const keys = [...map.keys()];
  // 升序排序，利用当前数字去找2倍的数字
  keys.sort((a: number, b: number) => Math.abs(a) - Math.abs(b));
  for (const num of keys) {
    // 如果倍数数量小于当前数字，表示不能满足条件
    if ((map.get(2 * num) || 0) < map.get(num)) return false;
    // 满足条件，更新倍数的数量，减去当前数字的数量
    map.set(2 * num, (map.get(2 * num) || 0) - map.get(num));
  }

  return true;
}
// @lc code=end
